package com.zyk.leetcode;

/**
 * @author zhangsan
 * @date 2021/4/25 9:41
 */
public class C9 {

    public static boolean isPalindrome(int x) {
        if (x < 0) return false;
        if (x < 10) return true;
        char[] str = manacherString(String.valueOf(x));
        return expand(str, str.length >> 1);
    }

    public static char[] manacherString(String str) {
        char[] charArr = str.toCharArray();
        char[] res = new char[str.length() * 2 + 1];
        int index = 0;
        for (int i = 0; i != res.length; i++) {
            res[i] = (i & 1) == 0 ? '#' : charArr[index++];
        }
        return res;
    }

    // 相对i位置开始往外扩, 从range为区间开始尝试, 返回最后扩到的右边界
    private static boolean expand(char[] str, int i) {
        int l, r = -1, range = 1;
        for (; (l = i - range) > -1 && (r = i + range) < str.length; range++)
            if (str[l] != str[r]) return false;
        return l == -1;
    }


    // for test
    public static void main(String[] args) {
        int x = 11;
        System.out.println(isPalindrome(x));
    }

}
